#include<stdio.h>
#include<stdlib.h>

/*
My favourite sort.
I won't delete it since I really like it.

void Radix(int* arr,const int n){
    int r1[256],r2[256],r3[256],r4[256];//1 2 3 4 
    int *tmp = (int*) malloc(kof(int) * (n + 2));
    for(int i=0;i<256;i++) r1[i] = r2[i] = r3[i] = r4[i] = 0;
    for(int* i = arr + 1,tmp;i != arr + n + 1;++i){
        tmp = *i;
        ++r1[tmp&255],++r2[(tmp>>8)&255],++r3[(tmp>>16)&255],++r4[tmp>>24];  
    }
    for(int i = 1;i<=255;++i)r1[i] += r1[i-1],r2[i] += r2[i-1],r3[i] += r3[i-1],r4[i] += r4[i-1];
    for(int* i=arr+n;i!=arr;--i)tmp[r1[*i & 255]--]=*i;
    for(int* i=tmp+n;i!=tmp;--i)arr[r2[(*i>>8)&255]--]=*i;
    for(int* i=arr+n;i!=arr;--i)tmp[r3[(*i>>16)&255]--]=*i;
    for(int* i=tmp+n;i!=tmp;--i)arr[r4[*i>>24]--]=*i;
    free(tmp);
}

void merge_arrays(const int *arr, int n, int k, int* output){
    int N = n * k;
    for(int i=0;i<N;i++) output[i] = arr[i];
    Radix(output - 1, N);
}
*/

#define ind(i, j) ((i) * n + (j))

typedef struct _minHeapNode {
    int v1, v2;
} node, *PMinHeapNode;

PMinHeapNode heap;

void swap_node(int i, int j) {
    int t1 = heap[j].v1, t2 = heap[j].v2;
    heap[j].v1 = heap[i].v1; 
    heap[j].v2 = heap[i].v2;
    heap[i].v1 = t1; 
    heap[i].v2 = t2;
}


void insert(int rt, int v1, int v2){
    heap[rt].v1 = v1; heap[rt].v2 = v2; 
    while(heap[rt / 2].v1 > heap[rt].v1) {
        if(rt == 0) break;
        swap_node(rt, rt / 2),
        rt /= 2;
    }
}

#define left(i) ((i) * 2 + 1)
#define right(i) ((i) * 2 + 2)

void min_heapify(int i, int k){
    if(left(i) >= k) return;
    if(left(i) == k - 1) {
        if(heap[left(i)].v1 < heap[i].v1)
            swap_node(i, left(i)),
            min_heapify(left(i), k);
    } else {
        int isLeft = heap[left(i)].v1 < heap[right(i)].v1;
        if(heap[i].v1 < heap[isLeft ? left(i) : right(i)].v1) return;
        swap_node(i, isLeft ? left(i) : right(i));
        min_heapify(isLeft ? left(i) : right(i), k);
    }
}

// You should notice that the real order of the params is different from the signature
void merge_arrays(const int *arr, int n, int k, int* output){
    int N = n * k;
    int *tmp = (int*) malloc(sizeof(int) * k);
    heap = (PMinHeapNode) malloc(sizeof(node) * k);
    for(int i=0;i<k;i++) {
        insert(i, arr[ind(i, 0)], i);
        tmp[i] = 0;
    }
    int MAX = 0;
    for(int i=0;i<N;i++) if(arr[i] >= MAX) MAX = arr[i] + 1;
    for(int i=0;i<N;i++) {
        output[i] = heap[0].v1;
        ++tmp[heap[0].v2];
        if(tmp[heap[0].v2] < n) heap[0].v1 = arr[ind(heap[0].v2, tmp[heap[0].v2])];
        else heap[0].v1 = MAX;
        min_heapify(0, k);
    }
}